#include <stdio.h>
#include <stdlib.h>
typedef struct stackNode{
	int pageNum;
	int stackSize;//栈的大小
	struct stackNode *next;
}stack,*P_Stack;
P_Stack initStack()
{
	P_Stack StackHead = (P_Stack)malloc(sizeof(stack));
	StackHead->pageNum = -1;
	StackHead->stackSize = 5;
	StackHead->next = NULL;
	return StackHead;
}
P_Stack Stack_Push(P_Stack StackHead ,int pageNum)//入栈
{
	P_Stack p = StackHead;
	while (p->next) {
		if(p->next->pageNum == pageNum)
				break;
		p = p->next;
	}
	
	if(p == NULL || p->next == NULL)
	{
			P_Stack new =(P_Stack) malloc(sizeof(stack));
			new->pageNum = pageNum;
			new->next = StackHead->next;
			StackHead->next = new;
			StackHead->stackSize--;
			return StackHead;
	}

	if(p == StackHead)//或本来就是第一个元素
	{
		return StackHead;
	}
	P_Stack first = StackHead->next;
	P_Stack aim = p->next;
	P_Stack aimNext = aim->next;
	
	StackHead->next = aim;
	aim->next = first;
	p->next = aimNext;
	
	return StackHead;
}
P_Stack Stack_Pop(P_Stack StackHead,int page)//出栈
{	
	P_Stack temp = StackHead->next;
	while(temp)
	{
		if(temp->pageNum == page)//如果内存不够了，并且要访问的页还是站里面的页，则不做操作
			break;
		temp = temp->next;
	}
	if(temp!=NULL)
	{
		return StackHead;
	}
	P_Stack p = StackHead->next;
	P_Stack aim = NULL;
	P_Stack pre;
		while(p->next)
			{
				pre = p;
				p = p->next;
			}
		aim = p;
		free(aim);
		pre->next = NULL;
		StackHead->stackSize++;
	return StackHead;
}
P_Stack LRU(P_Stack StackHead,int page)
{
	if(StackHead->stackSize < 1){//先判断栈是否满
		StackHead = Stack_Pop(StackHead,page);//满了抛出栈底元素
	}
	StackHead = Stack_Push(StackHead, page);//入栈
	return StackHead;
}
void printStack(P_Stack head)
{
	P_Stack p = head->next;
	while(p)
	{
		printf("%d\n",p->pageNum);
		p = p->next;
	}
}
int main(int argc, char *argv[]) {
	P_Stack h = initStack();
	while(1)
	{
		printf("请输入你的页码:");
		int pa;
		scanf("%d",&pa);
		h = LRU(h, pa);
		printStack(h);
	}
}